import java.util.*;


public class Test {
    // 最大连续1的个数
    public int longestOnes(int[] nums, int k) {
        int zero = 0, len = 0;
        for(int left = 0, right = 0; right < nums.length;right++){
            if(nums[right] == 0) zero++; //进窗口
            while(zero > k) // 做判断
                //无论if条件成不成立left++一定执行！！
                if(nums[left++] == 0) zero--; //出窗口
            len = Math.max(len,right - left + 1);  //更新结果 每次right++之前都要更新
        }
        return len;
    }

    //将x减到0的最小操作数
    public int minOperations(int[] nums, int x) {
        //先求nums数组的总和
        int sum = 0;
        for(int a : nums) sum += a;   //增强for
        int target = sum - x,len = -1;
        // 细节优化
        if(target < 0) return -1;
        //if(target == 0) return nums.length;  len改成-1之后就不需要额外判断
        for(int left = 0, right = 0, sumA = 0; right < nums.length; right++){
            //进窗口
            sumA += nums[right];
            //判断
            while(sumA > target) sumA -= nums[left++]; //出窗口
            //判断相等 取值
            if(sumA == target) len = Math.max(len,right - left + 1);
        }
        return len == -1 ? len : nums.length - len;
    }

    //水果盛篮（可以使用数组hash 来代替hashMap  可以很好的降低  时间复杂度和 空间复杂度）
    public int totalFruit(int[] fruits) {
        Map<Integer,Integer> hash = new HashMap<>(); //创建Hash表用来存放已经采摘的果树种类
        int len = 0;
        for(int left = 0, right = 0; right < fruits.length; right++){
            //进窗口
            int in = fruits[right];
            hash.put(in,hash.getOrDefault(in,0) + 1);
            //判断
            while(hash.size() > 2){
                //出窗口
                int out = fruits[left++];
                hash.put(out,hash.get(out) - 1);
                if(hash.get(out) == 0) hash.remove(out);
            }
            //求长度
            len = Math.max(len,right - left + 1);
        }
        return len;

    }

    //找到字符串中所有字母异位词(比较复杂！！！)
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        //定义两个hash表用来存放s和p包含的字符
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        //把字符串转换成字符数组
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        //将pp放入hash2中
        for(char ch : pp ) hash2[ch - 'a']++;
        int m = pp.length;
        //滑动窗口
        for(int left = 0, right = 0, count = 0; right < ss.length ; right++){
            //进窗口
            int in = ss[right] - 'a';
            if(++hash1[in] <= hash2[in]) count++;
            //判断(出窗口)
            if(right - left + 1 > m){
                int out = ss[left++] - 'a';
                if(hash1[out]-- <= hash2[out]) count--;
            }
            //更新结果
            if(count == m) list.add(left);
        }
        return list;
    }

    //串联所有单词的字串
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        //创建两个map集合
        Map<String,Integer> hash1 = new HashMap<>();
        for(String str : words) hash1.put(str,hash1.getOrDefault(str,0) + 1);
        //算出单个字符串长度
        int len = words[0].length(),m = words.length;
        //len 次滑动窗口
        for(int i = 0;i < len; i++){
            //单次滑动窗口  每次创建一个新的hash2
            Map<String,Integer> hash2 = new HashMap<>();
            for(int left = i, right = i,count = 0; right < s.length() - len + i; right += len){
                //进窗口
                String in = s.substring(right,right + len);
                hash2.put(in,hash2.getOrDefault(in,0) + 1);
                if(hash2.get(in) <= hash1.getOrDefault(in,0)) count++;
                //判断  出窗口
                if(right - left + 1 > len * m){
                    //出窗口
                    String out = s.substring(left, left + len);
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.get(out) - 1);
                    left += len;
                }
                if(count == m) list.add(left);
            }
        }
        return list;
    }

    //最小覆盖字串
    public String minWindow(String s, String t) {
        //创建两个hash表
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        //把t丢进hash1中 并计算种类
        char[] str1 = t.toCharArray();
        int countTKinds = 0,len = Integer.MAX_VALUE,leftN = -1;
        for(char ch : str1)
            if(hash1[ch]++ == 0) countTKinds++;
        //滑动窗口
        char[] str2 = s.toCharArray();
        for(int left = 0, right = 0, count = 0; right < str2.length; right++){
            //进窗口  把str2里面的字符丢进hash2中
            int in = str2[right];
            if(++hash2[in] == hash1[in]) count++;
            //判断  出窗口  更新结果
            while(count == countTKinds){
                //更新结果  记录最小长度  和left位置
                if(right - left + 1 < len){
                    len = right - left + 1;
                    leftN = left;
                }
                //出窗口
                int out = str2[left++];
                if(hash2[out]-- == hash1[out]) count--;
            }
        }
        if(leftN == -1) return new String();
        else  return s.substring(leftN,leftN+len);

    }

}
